class Solution {
public:
    unordered_map<long long, int> prefix; // 存储前缀和+次数
    int ret = 0;
    void dfs(TreeNode *root, long long sum, int targetSum) {
        if (root == nullptr)
            return;

        sum += root->val; // 计算当前路径的前缀和
        if (prefix.count(sum - targetSum)) // 检查是否存在满足sum - targetSum的前缀和
            ret += prefix[sum - targetSum];

        prefix[sum]++; // 将当前前缀和加入哈希表（用于后续节点查找）
        dfs(root->left, sum, targetSum);
        dfs(root->right, sum, targetSum);
        prefix[sum]--;// 回溯：移除当前前缀和（恢复状态）
    }

    int pathSum(TreeNode* root, int targetSum) {
        prefix[0] = 1; // 初始化：前缀和为0的情况出现1次（空路径）
        dfs(root, 0, targetSum);
        return ret;
    }
};